package com.notes.algo.t8;

import java.util.Arrays;

/**
 * @author
 * @Describe 功能描述
 * @date
 */
public class T1 {
    public static void main(String[] args) {
        int inf = 100;
        // 初始化节点数为7
        int node = 7;
        // 各个点之间的路径长度，inf表示不连通
        int[][] map = {
                // 从左往右，从上往下依次表示A、B、C、D、E、F、G
                {inf, 4, inf, inf, 7, inf, inf},
                {4, inf, 15, 3, inf, inf, inf},
                {inf, 15, inf, inf, inf, inf, 2},
                {inf, 3, inf, inf, 5, 3, 5},
                {7, inf, inf, 5, inf, 6, inf},
                {inf, inf, inf, 3, 6, inf, inf},
                {inf, inf, 2, 5, inf, inf, inf}};

        // 记录哪些点已经确定了，确定为true，否则为默认值false
        boolean[] isVisit = new boolean[node];
        // 记录每个点距离初始点的距离
        int[] distance = new int[node];
        // 初始值为inf，表示无穷大
        Arrays.fill(distance, inf);

        // 选择A作为初始点，0下标代表A，
        int initNode = 0;
        // A点到自己的距离为0
        distance[initNode] = 0;
        // 同时将isVisit数组元素A的下标0设置为true，表示A点已确定
        isVisit[initNode] = true;

        int currNode = initNode;
        int certainDistance = distance[currNode];
        // 只需计算其余6个点距离A点的距离，每次循环得到一个点，循环6次即可
        for (int loop = 1; loop < node; loop++) {
            // 循环计算和currNode有关系节点的距离，第一次currNode是A点
            for (int i = 0; i < map[currNode].length; i++) {
                // 以探索点距初始点的距离加上各点和探索点的距离更新distance矩阵
                int tmp = certainDistance + map[currNode][i];
                if (tmp < distance[i]) {
                    distance[i] = tmp;
                }
            }
            // 挑选还未访问，并且距离初始点最近的点作为探索点
            currNode = getMin(distance, isVisit, inf);
            // 将该探索点标记为true“已访问”，
            isVisit[currNode] = true;
            // 并且得到该点和A点的距离
            certainDistance = distance[currNode];
        }

        char[] str = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        for (int i = 0; i < node; i++) {
            System.out.println(str[i] + "到" + str[initNode] + "的距离为 " + distance[i]);
        }
    }

    static int getMin(int[] dis, boolean[] isVisit, int inf) {
        int min = -1;
        int minVal = inf;
        for (int i = 0; i < dis.length; i++) {
            // 扫描isVisit还未访问的节点，并且该节点是distance矩阵最小的数
            if ((!isVisit[i]) && (dis[i] < minVal)) {
                minVal = dis[i];
                min = i;
            }
        }
        return min;
    }
}
